public class Tire {
    private static class TrieNode {
        TrieNode[] children; // 子节点数组
        boolean isEnd;       // 是否是一个单词的结尾

        public TrieNode() {
            children = new TrieNode[26]; // 26 个小写字母
            isEnd = false;
        }
    }

    private TrieNode root; // 根节点

    public void Trie() {
        root = new TrieNode(); // 初始化根节点
    }

    public void insert(String word) {
        TrieNode node = root;
        for(char ch : word.toCharArray()){
            int index = ch - 'a';
            if(node.children[index] == null){
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        return node != null && node.isEnd; // 检查是否是一个单词的结尾
    }

    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    public TrieNode searchPrefix(String word){
        TrieNode node = root;
        for(char ch : word.toCharArray()){
            if(node.children[ch - 'a'] ==null){
                return null;
            }
            node = node.children[ch - 'a'];
        }
        return node;
    }
}
